package Hot100.Easy.LC21;

/**
 * 合并两个有序链表
 */
public class LC21 {
    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.next=new ListNode(2);
        l1.next.next=new ListNode(4);

        ListNode l2=new ListNode(1);
        l2.next=new ListNode(3);
        l2.next.next=new ListNode(4);
        LC21 solution = new LC21();
        //这里的result实际上是合并后链表的头节点
        ListNode result=solution.mergeTwoLists(l1,l2);
//        while(result!=null){
//            System.out.println(result.val);
//            result=result.next;
//        }
        solution.PrintList(result);

    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode fakehead = new ListNode(0);
        ListNode p = fakehead;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                p.next=l1;
                l1=l1.next;
                p=p.next;
            }
            else{
                p.next=l2;
                l2=l2.next;
                p=p.next;
            }
        }
        p.next=l1==null? l2:l1;
        return fakehead.next;

    }

    public void PrintList(ListNode head){
        while(head!=null){
            System.out.print(head.val+" ");
            head=head.next;
        }

    }
}
